package com.fw.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序 - 经典
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {-2321,2,0,3,56,-2,123};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }


    /**
     * 快速排序思路刨析
     * @param arr
     * @param leftIndex
     * @param rightIndex
     *
     * 1. 拿到排序的队列 中间位置的元素值。
     * 2. 左小右大的思路，左边的那个比 中间元素大，右边元素比中间元素小的话，就进行交换。
     * 3. 继续分裂，把左边再取一个值继续重复步骤。
     * 4. 右边一致。
     */
    public static void quickSort(int arr[],int leftIndex,int rightIndex){
        int l = leftIndex;
        int r = rightIndex;
        // 得到中间元素
        int centVal = arr[(l + r) /2];
        // 临时值
        int tempVal = 0;
        // 进行循环操作
        while (l < r){
            // 左边的数据一直找，找到比 centVal 大的。
            // 千万不能加 = 否则，一旦左边的值，都小于 中间值，下标异常了。
            while (arr[l] < centVal){
                l +=1;
            }
            // 右边数据一直找，找到比 centVal 小的。
            while (arr[r] > centVal){
                r -=1;
            }
            //如果 l >= r 说明 centVal 的左右两的值，已经按照左边全部是
            // 小于等于 centVal 值，右边全部是大于等于 centVal 值
            if (l >= r) break;
            // 进行交换
            tempVal = arr[l];
            arr[l] = arr[r];
            arr[r] = tempVal;

            //如果交换完后，发现这个 arr[l] == pivot 值 相等 r--， 前移
         if(arr[l] == centVal) {
            r -= 1;

         }
         //如果交换完后，发现这个 arr[r] == pivot 值 相等 l++， 后移
        if(arr[r] == centVal) {
           l += 1;
        }

            // 如果 l == r, 必须 l++, r--, 否则为出现栈溢出
            if (l == r) {
            l += 1;
            r -= 1;
            }
            // 开始递归
            // 想左递归
            if (leftIndex < r){
                quickSort(arr,leftIndex,r);
            }
            // 右递归
            if (rightIndex > l){
                quickSort(arr,l,rightIndex);
            }




        }
    }
}
